/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Aug 27, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given an index k, return the kth row of the Pascal's triangle.
 * 
 *              For example, given k = 3, Return [1,3,3,1].
 * 
 *              Note: Could you optimize your algorithm to use only O(k) extra
 *              space?
 */
public class PascalTriangleII {

	public List<Integer> getRow(int rowIndex) {
		int[] res = new int[rowIndex + 1];  
        res[0] = 1;  
        for(int i = 1; i <= rowIndex; i++){  
            for(int j = i; j > 0; j--){  
                if(j == i)  
                    res[j] = 1;  
                else  
                    res[j] = res[j - 1] + res[j];  
            }  
        }  
        ArrayList<Integer> res_list = new ArrayList<Integer>();  
        for(int i = 0; i < res.length; i++)  
            res_list.add(res[i]);  
        return res_list;  
    }

	@Test
	public void test() {
		List<Integer> res = getRow(24);
		for (int i : res) {
			System.out.print(i + ",");
		}
	}
}
